/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/max-points-on-a-line
   @Language: C++
   @Datetime: 19-11-20 15:39
   */

class Solution {
	struct Fraction{
		int num, den;    // numerator, denominator
		bool sign;
		Fraction(int n, int d, bool s=true):num(n),den(d),sign(s){}
	};
	struct FractionHash{
		static int gcd(int a, int b){
			if(a==0 || b==0) return a?a:b;
			return gcd(b,a%b);
		}
		bool operator()(const Fraction &a, const Fraction &b)const{
			return (a.sign?1L:-1L)*a.num*b.den==(b.sign?1L:-1L)*b.num*a.den;    // math
		}
		size_t operator()(const Fraction &f)const{
			int r=gcd(f.num,f.den);
			if(r==0) return 0;    // 0/0
			long n=labs(1L*f.num/r), d=labs(1L*f.den/r);
			return (n<<32)|d;
		}
	};
public:
	int maxPoints(vector<vector<int>>& points) {
		int mx=0;
		for(const auto &p:points){
			int x=p[0], y=p[1], pc=0, m=0;
			unordered_map<Fraction,int,FractionHash,FractionHash> ks;
			for(const auto &q:points){
				if(!(p==q)){
					Fraction k(x-q[0], y-q[1]);
					m=max(m,++ks[k]);    // line k's points except p
				}
				else ++pc;    // point p count
			}
			mx=max(mx,m+pc);
		}
		return mx;
	}
};

